|
The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks. It can be used to check that data transmissions, in the form of packets,〔 conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler. The leaky bucket algorithm is also used in leaky bucket counters, e.g. to detect when the average or peak rate of random or stochastic events or stochastic processes exceed defined limits. A version of the leaky bucket, the Generic Cell Rate Algorithm, is recommended for Asynchronous Transfer Mode (ATM) networks〔 in Usage/Network Parameter Control at User–Network Interfaces or Inter-Network Interfaces or Network-Network Interfaces to protect a network from excessive traffic levels on connections routed through it. The Generic Cell Rate Algorithm, or an equivalent, may also be used to shape transmissions by a Network Interface Card onto an ATM network (i.e. on the user side of the User-Network Interface), e.g. to levels below the levels set for Usage/Network Parameter Control in the network to prevent it taking action to further limit that connection. ==Overview== The Leaky Bucket Algorithm is based on, and gets it name from, an analogy of a bucket (figure 1) that has a hole in the bottom through which any water it contains will leak away at a constant rate, until or unless it is empty. Water can be added intermittently, i.e. in bursts, but if too much is added at once, or it is added at too high an average rate, the water will exceed the capacity of the bucket, which will overflow. Hence, this leaky bucket determines whether adding some amount of water would exceed or conform to a limit on the average rate at which water can be added, set by the leak rate, and a limit on how much water can be added in a burst, set by the depth of the bucket. Two different methods of applying this leaky bucket analogy are described in the literature.〔〔〔〔 These give what appear to be two different algorithms, both of which are referred to as the leaky bucket algorithm and generally without reference to the other method. This has resulted in confusion about what the leaky bucket algorithm is and what its properties are. In one version of applying the analogy, the analogue of the bucket is a counter or variable, separate from the flow of traffic or scheduling of events.〔〔〔 This counter is used only to check that the traffic or events conform to the limits: The counter is incremented as each packet arrives at the point where the check is being made or an event occurs, which is equivalent to the way water is added intermittently to the bucket. The counter is also decremented at a fixed rate, equivalent to the way the water leaks out of the bucket. As a result, the value in the counter when a packet arrives indicates its conformance to the bandwidth and burstiness limits or when an event occurs, its conformance to the average and peak rate limits. So in this version, the analogue of the water is carried by the packets or the events, added to the bucket on their arriving or occurring, and then leaks away. This version is referred to here as the leaky bucket as a meter. In the second version, the analogue of the bucket is a queue in the flow of traffic.〔 This queue is used to directly control that flow: Packets are entered into the queue as they arrive, equivalent to the water being added to the bucket. These packet are then removed from the queue (first come, first served), usually at a fixed rate, e.g. for onward transmission, equivalent to water leaking from the bucket. As a result, the rate at which the queue is serviced directly controls the onward transmission rate of the traffic. Thus it imposes conformance rather than checking it, and where the queue is serviced at a fixed rate (and where the packets are all the same length), the resulting traffic stream is necessarily devoid of burstiness or jitter. So in this version, the traffic itself is the analogue of the water passing through the bucket. It is not clear how this version of applying the analogy might be used to the check the rates of discrete events. This version is referred to here as the leaky bucket as a queue. The leaky bucket as a meter is exactly equivalent to (a mirror image of) the token bucket algorithm, i.e. the process of adding water to the leaky bucket exactly mirrors that of removing tokens from the token bucket when a conforming packet arrives, the process of leaking of water from the leaky bucket exactly mirrors that of regularly adding tokens to the token bucket, and the test that the leaky bucket will not overflow is a mirror of the test that the token bucket contains enough tokens and will not 'underflow'. Thus, given equivalent parameters, the two algorithms will see the same traffic as conforming or nonconforming. The leaky bucket as a queue can be seen as a special case of the leaky bucket as a meter.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「leaky bucket」の詳細全文を読む スポンサード リンク
|